package com.company;

/**
 * @author zhf
 * @date 2021/11/22
 */

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 */
public class MaxRectangle {
    public static void main(String[] args) {
        //int[] heights = new int[]{2,1,5,6,2,3};
        int[] heights = new int[]{2,4};

        MaxRectangle maxRectangle = new MaxRectangle();
        int ans = maxRectangle.largestRectangleArea(heights);
        System.out.println(ans);
    }
    /*
    单调栈
     */
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
//        Stack<Integer> stack = new Stack<>();?
        int len = heights.length;
        int[] left = new int[len];
        int[] right = new int[len];
        int Maxarea = 0;
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = len - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();
            }
            right[i] = stack.isEmpty() ? len : stack.peek();
            stack.push(i);
        }
        for (int i = 0; i < len; i++) {
            Maxarea = Math.max(Maxarea,heights[i] * (right[i] - left[i] - 1));
        }
        return Maxarea;
    }
}
